#include <iostream>
#include <vector>
#include <climits>
#include <fstream>
#include <sstream>
#include <string>
using namespace std; // 辅助函数：计算两个矩阵相乘的代价
int calculateCost(int rows1, int cols1, int cols2)
{
  return rows1 * cols1 * cols2;
} // 分治函数：计算矩阵链乘法的最小代价，并记录最优括号化方案
pair<int, string> matrixChainDivideAndConquer(const vector<int> &dims, int i, int j)
{
  if (i == j)
  {                                           // 只有一个矩阵，代价为0
    return {0, "(" + to_string(i - 1) + ")"}; // 修正为0-based索引
  }
  int min_cost = INT_MAX;
  string best_parens; // 尝试在每一个可能的位置k进行分割
  for (int k = i; k < j; k++)
  { // 递归计算左子问题的代价和括号化方案
    pair<int, string> left = matrixChainDivideAndConquer(dims, i, k);
    int left_cost = left.first;
    string left_parens = left.second; // 递归计算右子问题的代价和括号化方案
    pair<int, string> right = matrixChainDivideAndConquer(dims, k + 1, j);
    int right_cost = right.first;
    string right_parens = right.second; // 计算当前分割的代价
    int q = dims[i - 1] * dims[k] * dims[j];
    int total_cost = left_cost + right_cost + q; // 如果当前代价更小，则更新最优解
    if (total_cost < min_cost)
    {
      min_cost = total_cost; // 构建正确的括号化方案
      best_parens = "(" + left_parens + right_parens + ")";
    }
  }
  return {min_cost, best_parens};
}
int main()
{
  vector<int> dims;
  string fileName = "../data/matrix_chain-github-input_03.txt";
  ifstream inputFile(fileName);
  if (!inputFile)
  {
    cerr << "无法打开文件: " << fileName << endl;
    return 1;
  }
  int numMatrices;
  inputFile >> numMatrices; // 读取矩阵数量
  int rows, cols;
  inputFile >> rows >> cols; // 读取第一个矩阵的维度
  dims.push_back(rows);
  dims.push_back(cols); // 读取剩余矩阵的维度
  for (int i = 1; i < numMatrices; i++)
  {
    inputFile >> rows >> cols;
    dims.push_back(cols); // 只需存储前一个矩阵的列和当前矩阵的列
  }
  inputFile.close();
  if (dims.size() < 2)
  {
    cerr << "错误: 矩阵维度数据不足" << endl;
    return 1;
  } // 调用分治函数
  pair<int, string> result = matrixChainDivideAndConquer(dims, 1, dims.size() - 1);
  cout << "最优标量乘法次数（分治）: " << result.first << endl;
  cout << "最优括号化方案（分治）: " << result.second << endl;
  return 0;
}